The present invention relates to an encoding device, an encoding method, an encoding program, a decoding device, a decoding method, and a decoding program. In particular, the present invention is applicable to serial concatenated coding and serial concatenated trellis coded modulation. In the present invention, in second coding, which is inner coding, a sequence that is not coded or that is coded so as to produce a finite impulse response and a sequence that is coded so as to produce an infinite impulse response are output, and, in interleaving before the second encoding, the sequences are permuted so as not to be mixed with each other, thus improving the performance over the related art.
With the recent research and development in the communication field including mobile communications and deep space communications, the broadcasting field including terrestrial digital broadcasting and satellite digital broadcasting, recording and playback apparatuses, and so forth, studies on coding theory have been extensively conducted for the purpose of efficient error-correcting coding and decoding.
In such coding theory, the so-called Shannon limit is known, which is given by the Shannon's channel coding theorem. The Shannon's channel coding theorem shows one theoretical limit of code performance, which indicates the theoretical limit of transmission rate that permits transmission without error. The Shannon's channel coding theorem is that “there exists a coding scheme that yields an error probability as close to “0” as possible if R≦C, where information is transmitted at a transmission rate R [bit/symbol] using a communication channel with a channel capacity C [bit/symbol].”
One known coding scheme that shows performance near the Shannon limit is coding of serial concatenated convolutional codes (hereinafter referred to as SCCC), which is described in, for example, S. Benedetto, G. Montorsi, D. Divsalar, and F. Pollara, “Serial Concatenation of Interleaved Codes: Performance Analysis, Design, and Iterative Decoding”, TDA Progress Report 42-126, Jet Propulsion Laboratory, Pasadena, Calif., Aug. 15, 1996.
Coding of serial concatenated convolutional codes is performed by a device including a serial concatenation of a first convolutional encoder, an interleaver, and a second convolutional encoder. Decoding of serial concatenated convolutional codes is performed by a device including two decoding circuits that output soft-output, which are connected via a de-interleaver and an interleaver.
One known application of coding of serial concatenated convolutional codes is serial concatenated trellis coded modulation (hereinafter referred to as SCTCM), which is described in, for example, D. Divsalar and F. Pollara, “Serial and Hybrid Concatenation Codes with Applications”, in Proc., Int. Symp. on Turbo Codes and Related Topics, Brest, France, pp. 80-87, September 1997. The SCTCM coding is a combination of coding of serial concatenated convolutional codes and multi-level modulation, and takes into consideration the entirety of the code constellation of modulated codes and the decoding characteristics of error-correcting codes.
FIG. 1 is a block diagram of a communication model in SCCC and SCTCM. In such a communication model, an encoding device 2 in a transmitter encodes digital information D1 with serial concatenated convolutional codes, and transmits the encoded output D2 to a receiver via a noisy memoryless channel 3, and then a decoding device 4 in the receiver decodes the transmitted output D3. In SCCC and SCTCM, an SCCC encoding device 2A and decoding device 4A and an SCTCM encoding device 2B and decoding device 4B, which correspond to the encoding device 2 and the decoding device 4, are used, respectively.
FIG. 2 is a block diagram of the SCCC encoding device 2A. The encoding device 2A includes a serial concatenation of a convolutional encoder 5 for encoding a first code, which is an outer code, an interleaver 6, and a convolutional encoder 7 for encoding a second code, which is an inner code. In the encoding device 2A, the convolutional encoder 5 performs convolutional coding on input data D1 with code rate 1/2 to convert the 1-bit input data D1 into 2-bit coded output data D6, and outputs the result.
FIG. 3 is a block diagram showing the structure of the convolutional encoder 5. In the convolutional encoder 5, the input data D1 is input to a series circuit of an exclusive OR circuit 8 and shift registers 9 and 10. The output data of the shift registers 9 and 10 are exclusive ORed by an exclusive OR circuit 11, and the resulting exclusive OR is then input to the exclusive OR circuit 8. The outputs of the exclusive OR circuit 8 and the shift register 10 are exclusive ORed by an exclusive OR circuit 12. The convolutional encoder 5 outputs the input data D1 and the output data of the exclusive OR circuit 12 to the subsequent interleaver 6. In the convolutional encoder 5, therefore, the input data D1 is convolutional coded with code rate 1/2, and the two bit sequences of output data D6 is output.
The interleaver 6 interleaves and permutes the order of the output data D6 output from the convolutional encoder 5, and outputs the result. FIG. 4 is a block diagram of an example structure of the interleaver 6. In the interleaver 6, the output data D6 of the convolutional encoder 5 is temporarily stored in an input data storage memory 15, and is then input to a subsequent data permuting circuit 16. The data permuting circuit 16 permutes the order of the output data from the input data storage memory 15 based on data permutation position information recorded in a permutation data ROM (Read Only Memory) 17, and outputs the result. The output data of the data permuting circuit 16 is temporarily stored in a subsequent output data storage memory 18, and is then output.
The convolutional encoder 7 performs convolutional coding on the output data D7 of the interleaver 6 with code rate 2/2, and outputs the output data D2. FIG. 5 is a block diagram showing an example structure of the convolutional encoder 7. In the convolutional encoder 7, the sequences of output data D7 from the interleaver 6 are input to a series circuit of an exclusive OR circuit 21 and a shift register 22, and to a series circuit of an exclusive OR circuit 23 and a shift register 24, respectively. The output data of the shift registers 22 and 24 are fed back to the exclusive OR circuits 21 and 23. Moreover, on the side of one sequence, the output data of the shift register 24 on the side of the other sequence is fed back to the exclusive OR circuit 21, and on the side of the other sequence, the output data of the exclusive OR circuit 21 on the side of one sequence is fed back to the exclusive OR circuit 23. In this manner, the convolutional encoder 7 performs convolutional coding on the output data D7 of the interleaver 6 with code rate 2/2.
Accordingly, the convolutional encoders 5 and 7 perform coding with code rates 1/2 and 2/2, and, finally, the encoding device 2A performs serial concatenated convolutional coding with code rate (1/2)×(2/2)=1/2. The serial-concatenated convolutional coded output data is input to the decoding device 4A in the receiver via the memoryless channel 3.
FIG. 6 is a block diagram showing an example structure of the SCCC decoding device 4A. The decoding device 4A includes soft-output decoding circuits 33 and 34 that decode an inner code and an outer code, respectively, which are connected via a de-interleaver 31 and an interleaver 32. In the decoding device 4A, the data D3 from the memoryless channel 3 is input to the soft-output decoding circuit 33 that decodes an inner code. The data D3 from the memoryless channel 3 contains the noise generated in the memoryless channel 3. In the decoding device 4A, the data D3 and the output data of the interleaver 32 that take analog values are input, as soft-inputs, to the soft-output decoding circuit 33.
The soft-output decoding circuit 33 corresponds to the convolutional encoder 7 of the encoding device 2A, and performs MAP (maximum a-posteriori probability) decoding, SOVA (soft-output Viterbi algorithm) decoding, or the like, based on the so-called BCJR (Bahl, Cocke, Jelinek, and Raviv) algorithm. The soft-output decoding circuit 33 receives soft-input information bits D8 that are supplied from the interleaver 32 as a-priori probability information, and sequentially processes the a-priori probability information and the received word, i.e., the output data D3, of the memoryless channel 3 in accordance with the code constraint condition, thereby performing soft-output decoding on the inner code. In this manner, the soft-output decoding circuit 33 outputs the soft-output D9, which corresponds to the output data D7 of the interleaver 6 in the encoding device 2A.
The de-interleaver 31 corresponds to the interleaver 6 of the encoding device 2A, and reversely reorders the soft-output D9 output from the soft-output decoding circuit 33 to the input/output order as in the interleaver 6, and outputs the result.
The subsequent soft-output decoding circuit 34 corresponds to the convolutional encoder 5 of the encoding device 2A. Like the soft-output decoding circuit 33, the soft-output decoding circuit 34 performs MAP decoding, SOVA decoding, or the like based on the BCJR algorithm. Specifically, the soft-output decoding circuit 34 uses the a-priori probability information, which is soft-input D10 of the de-interleaver 31, and a-priori probability information, which corresponds to an information bit of value “0”, to perform soft-output decoding on the outer code in order to output hard-output decoded data D4. In the processing, the soft-output decoding circuit 34 generates a-posteriori probability information D11 that corresponds to the coded bits in accordance with the code constraint condition, and outputs the a-posteriori probability information D11, as soft-output, to the interleaver 32. The interleaver 32 permutes the a-posteriori probability information D11 according to the same order as in the interleaver 6 of the encoding device 2A, and outputs the a-priori probability information D8 to the soft-output decoding circuit 33.
With the structure described above, upon receiving the received word D3, the decoding device 4A iterates the decoding processing of the soft-output decoding circuit 33 to the soft-output decoding circuit 34 a predetermined number of times (for example, several times to tens of times), and outputs the decoded data D4 based on the soft-output extrinsic information obtained by the iterative decoding.
FIG. 7 is a block diagram showing an example structure of the SCTCM encoding device 2B. The encoding device 2B includes a serial concatenation of an outer-code convolutional encoder 41, an interleaver 42, an inner-code convolutional encoder 43, and a multi-level modulation mapping circuit 44.
The outer-code convolutional encoder 41 performs convolutional coding on input data D1 with code rate 2/3 to convert the 2-bit input data D1 into 3-bit coded output data D21, and outputs the result.
As shown in FIG. 8, in the convolutional encoder 41, an exclusive OR circuit 51 determines the exclusive OR of the input data D1 (D11 and D12), and the result of the exclusive OR circuit 51 is input to an exclusive OR circuit 53 via a shift register 52. The exclusive OR circuit 53 determines the exclusive OR of this result and the bit sequence D11 of the input data D1. The result of the exclusive OR circuit 53 is input to an exclusive OR circuit 55 via a shift register 54. The exclusive OR circuit 55 determines the exclusive OR of the result of the exclusive OR circuit 53 and the two bit sequences D11 and D12 of the input data D1 to generate a bit sequence D213. The convolutional encoder 41 outputs the bit sequence D213 and the two bit sequences D11 and D12 of the input data D1 (i.e., D211 and D212), thus performing convolutional coding with code rate 2/3.
The interleaver 42 has a structure similar to that of the interleaver 6 described above with reference to FIG. 4, and permutes the order of the output data D21 output from the convolutional encoder 41 before outputting the data.
The inner-code convolutional encoder 43 performs convolutional coding on output data D22 of the interleaver 42 with code rate 3/3 to output data D23. As shown in FIG. 9, in the convolutional encoder 43, three bit sequences D221 to D223 constituting the output data D22 of the interleaver 42 are input to an exclusive OR circuit 56 to determine the exclusive OR of these bit sequences and the output data of a shift register 57. The output of the exclusive OR circuit 56 is fed back to the shift register 57. The convolutional encoder 43 outputs the exclusive ORed bit sequence D233 and the two bit sequences D222 and D223 of the input data D22 (i.e., D231 and D232), thus performing convolutional coding with code rate 3/3.
The multi-level modulation mapping circuit 44 maps signal points using a predetermined modulation method. Specifically, the multi-level modulation mapping circuit 44 maps the 3-bit output data D23 output from the convolutional encoder 43 onto a transmission symbol using, for example, 8PSK (8-phase shift keying) modulation. The encoding device 2B transmits the output data D2 of the multi-level modulation mapping circuit 44 to a communicating party.
Accordingly, the convolutional encoders 41 and 43 perform coding with code rates 2/3 and 3/3, respectively, and, finally, the encoding device 2B performs serial concatenated convolutional coding with code rate 2/3 to output the output data D2.
FIG. 10 is a block diagram showing an example structure of the SCTCM decoding device 4B. The decoding device 4B includes soft-output decoding circuits 63 and 64 that decode an inner code and an outer code, respectively, which are connected via a de-interleaver 61 and an interleaver 62. In the decoding device 4B, the data D3 from the memoryless channel 3 is input to the soft-output decoding circuit 63 that decodes an inner code. The data D3 from the memoryless channel 3 contains the noise generated in the memoryless channel 3. In the decoding device 4B, the data D3 and output data D34 of the interleaver 32 that take analog values are input, as soft-inputs, to the soft-output decoding circuit 63.
The soft-output decoding circuit 63 corresponds to the convolutional encoder 43 and the multi-level modulation mapping circuit 44 of the encoding device 2B, and sequentially processes soft-input information bits D34, which are supplied from the interleaver 62, and the received word, i.e., the output data D3, of the memoryless channel 3 by MAP decoding, SOVA decoding, or the like based on the so-called BCJR algorithm to perform soft-output decoding on the inner code. In this manner, the soft-output decoding circuit 63 outputs the soft-output D31 which corresponds to the output data D22 of the interleaver 42 in the encoding device 2A.
The de-interleaver 61 corresponds to the interleaver 42 of the encoding device 2B, and reversely reorders the soft-output D31 output from the soft-output decoding circuit 63 to the input/output order as in the interleaver 42, and outputs the result.
The subsequent soft-output decoding circuit 64 corresponds to the convolutional encoder 41 of the encoding device 2B. Like the soft-output decoding circuit 63, the soft-output decoding circuit 64 performs MAP decoding, SOVA decoding, or the like based on the BCJR algorithm to perform soft-output decoding on the outer code in order to output hard-output decoded data D4. The soft-output decoding circuit 64 further generates a-posteriori probability information D33 that corresponds to the coded bits, and outputs the a-posteriori probability information D33, as soft-output, to the interleaver 62. The interleaver 62 permutes the a-posteriori probability information D33 according to the same order as in the interleaver 42 of the encoding device 2B, and outputs a-priori probability information D34 to the soft-output decoding circuit 63.
With the structure described above, upon receiving the received word D3, likewise, the decoding device 4B iterates the decoding processing of the soft-output decoding circuit 63 to the soft-output decoding circuit 64 a predetermined number of times, and outputs the decoded data D4 based on the soft-output extrinsic information obtained by the iterative decoding.
However, such SCCC and SCTCM systems have a problem in that there is a large difference between the logical limit and the actual performance, and therefore, there is still room for improvement in the performance.
FIGS. 11 and 12 show the performances of the SCCC and SCTCM systems, respectively, in relation to the signal-to-noise power ratio (Eb/No) per bit and the bit error rate on the x-axis and the y-axis, respectively. The performance of the SCTCM system is obtained in a case where the signal points are mapped by the multi-level modulation mapping circuit 44 onto the constellation shown in FIG. 13, wherein the sum of input distances between codewords, that is, minimum Euclidean distances, is 16.
As shown in FIG. 11, the SCCC system exhibits the so-called waterfall phenomenon at a signal-to-noise power ratio (Eb/No) of about 2.0 dB. The waterfall phenomenon is a phenomenon wherein the error rate rapidly drops from as high as about 10−1 as the signal-to-noise power ratio (Eb/No) increases. The theoretical limit for the code rate of this system is about 0.2 dB, and therefore, there is still room for improvement in the performance.
As shown in FIG. 12, the SCTCM system exhibits the waterfall phenomenon at a signal-to-noise power ratio (Eb/No) of about 3.4 dB. The theoretical limit for the code rate of this system is about 2.8 dB, and therefore, also, there is still room for improvement in the performance.